package leetcode51_60;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author shhjiang_001
 * @create 2020-06-18 14:00
 */
        /*
        n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
        上图为 8 皇后问题的一种解法。
        给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
        每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
        示例:
        输入: 4
        输出: [
        [".Q..",  // 解法 1
        "...Q",
        "Q...",
        "..Q."],
        ["..Q.",  // 解法 2
        "Q...",
        "...Q",
        ".Q.."]
        ]
        解释: 4 皇后问题存在两个不同的解法。
        */

public class Solution51 {
    List<List<String>> resList = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] chars = new char[n][n];
        for (int i = 0;i < n;i++){
            for (int j = 0;j < n;j++){
                chars[i][j] = '.';
            }
        }
        int i= 0,j =0;
        int num = 0;
        method(chars,i,j,num);
        return resList;
    }

    private void method(char[][] chars, int i, int j, int num) {
        if (num == chars.length){
            // 把符合的结果加到结果数组中
            ArrayList<String> strings = new ArrayList<>();
            for (int m = 0;m < chars.length;m++){
                String s1 = new String(chars[m]);
//                String s = Arrays.toString(chars[m]);
                strings.add(s1);
            }
            resList.add(strings);
            return;
        }
        if (i == chars.length) return;
        boolean isFlag = true;
        int leRow = i-7>=0?i-7:0;
        int riRow = i+7<=chars.length-1?i+7:chars.length-1;
        int leLine = j-7>=0?j-7:0;
        int riLine = j+7<=chars.length-1?j+7:chars.length-1;
        // 判断行
        for (int m = leRow;m < riRow;m++){
            if (chars[m][j] == 'Q'){
                isFlag = false;
                break;
            }
        }
        // 判断列
        for (int m = leLine;m < riLine;m++){
            if (chars[i][m] == 'Q'){
                isFlag = false;
                break;
            }
        }

        int le = i;
        int ri = j;
        while (le < chars.length && le >=0 && ri >= 0 && ri < chars.length){
            if (chars[le][ri] == 'Q') {
                isFlag = false;
                break;
            }
            le++;
            ri++;
        }
        le = i;
        ri = j;
        while (le < chars.length && le >=0 && ri >= 0 && ri < chars.length){
            if (chars[le][ri] == 'Q') {
                isFlag = false;
                break;
            }
            le--;
            ri++;
        }
        le = i;
        ri = j;
        while (le < chars.length && le >=0 && ri >= 0 && ri < chars.length){
            if (chars[le][ri] == 'Q') {
                isFlag = false;
                break;
            }
            le++;
            ri--;
        }
        le = i;
        ri = j;
        while (le < chars.length && le >=0 && ri >= 0 && ri < chars.length){
            if (chars[le][ri] == 'Q') {
                isFlag = false;
                break;
            }
            le--;
            ri--;
        }
        if (isFlag){
            chars[i][j] = 'Q';
            num++;
            if (j==chars.length-1){
                method(chars,i+1,0,num);
                chars[i][j] = '.';
                num--;
                method(chars,i+1,0,num);
            }else {
                method(chars,i,j+1,num);
                chars[i][j] = '.';
                num--;
                method(chars,i,j+1,num);
            }
        }else {
            if (j==chars.length-1){
                method(chars,i+1,0,num);
//                chars[i][j] = '.';
            }else {
                method(chars,i,j+1,num);
//                chars[i][j] = '.';
            }
        }



    }
    @Test
    public void test() {
        Solution51 solution51 = new Solution51();
//        System.out.println(Arrays.asList(new int[]{1, 2, 3}).toString());
        solution51.solveNQueens(4);
    }
}
